let words = ['oath', 'pea', 'eat', 'rain']

let board = [
  ['o', 'a', 't', 'h'],
  ['e', 't', 'a', 'e'],
  ['i', 'h', 'k', 'r'],
  ['i', 'f', 'l', 'v'],
]

class Trie {
  constructor() {
    this.root = Object.create(null)
    this.endOfWord = Symbol('endOfWord')
  }
  insert(word) {
    let node = this.root
    for (let w of word) {
      if (!node[w]) {
        node[w] = Object.create(null)
      }
      node = node[w]
    }
    if (!node[this.endOfWord]) {
      node[this.endOfWord] = 0
    }
    node[this.endOfWord] += 1
  }
  search(word) {
    let node = this.root
    for (let w of word) {
      if (!node[w]) return false
      node = node[w]
    }
    return !!node[this.endOfWord]
  }
}

function wordSearch(words, board) {
  // 生成Trie数据结构，用来保存words
  let trie = new Trie()
  for (let w of words) {
    trie.insert(w)
  }

  // 遍历 board
  let m = board.length
  let n = board[0].length
  let result = []
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (trie.root[board[i][j]]) {
        dfs(board, i, j, '', trie.root)
      }
    }
  }

  //   function dfs(board, i, j, curWord, curDict) {
  //     curWord += board[i][j]
  //     curDict = curDict[board[i][j]]
  //   }

  return result
}
